#include <stdio.h>
#include <stdlib.h>

// 线索二叉树：加快查找前驱或后继的速度，将非线性结构线性化

typedef char ElemType;

// 线索二叉树节点结构体
typedef struct ThreadNode
{
    ElemType data;          // 节点数据
    struct ThreadNode *lchid; // 左孩子指针/前驱线索
    struct ThreadNode *rchid; // 右孩子指针/后继线索
    int ltag;               // 左标记：0=指向左孩子，1=指向前驱
    int rtag;               // 右标记：0=指向右孩子，1=指向后继
} ThreadNode;

typedef ThreadNode* ThreadTree;

// 用于构建二叉树的前序遍历字符串（#表示空节点）
char str[] = "ABDH##I##EJ###CF##G##";
int idx = 0;               // 字符串索引，记录当前处理位置
ThreadTree prev;           // 线索化过程中，记录上一个访问的节点

// 创建二叉树（前序遍历方式）
void createTree(ThreadTree *T)
{
    ElemType ch;
    ch = str[idx++];        // 读取当前字符并移动索引

    if (ch == '#')
    {
        *T = NULL;          // 空节点
    }
    else
    {
        // 修复：分配整个ThreadNode的大小，而非指针大小
        *T = (ThreadTree)malloc(sizeof(ThreadNode));
        if (*T == NULL)
        {
            printf("内存分配失败\n");
            exit(1);
        }
        (*T)->data = ch;    // 赋值当前节点数据

        // 递归创建左子树
        createTree(&(*T)->lchid);
        // 左孩子存在则标记为0，否则标记为1（线索）
        (*T)->ltag = ((*T)->lchid != NULL) ? 0 : 1;  
        /*
            上面的式子是三目运算符，等价于下面语句：
            if ((*T)->lchid != NULL) {
            (*T)->ltag = 0;  // 条件为真时执行
            } else {
            (*T)->ltag = 1;  // 条件为假时执行
             }
        */
        // 递归创建右子树
        createTree(&(*T)->rchid);
        // 右孩子存在则标记为0，否则标记为1（线索）
        (*T)->rtag = ((*T)->rchid != NULL) ? 0 : 1;
    }
}

// 中序线索化（核心：处理当前节点与前驱的线索关系）
void threading(ThreadTree T)
{
    if (T != NULL)
    {
        threading(T->lchid);  // 先线索化左子树

        // 左孩子为空时，左指针作为前驱线索，指向prev（上一个节点）
        if (T->lchid == NULL)
        {
            T->ltag = 1;
            T->lchid = prev;
        }

        // 前驱节点的右孩子为空时，右指针作为后继线索，指向当前节点T
        if (prev != NULL && prev->rchid == NULL)
        {
            prev->rtag = 1;
            prev->rchid = T;
        }

        prev = T;  // 更新prev为当前节点，供下一个节点使用

        threading(T->rchid);  // 线索化右子树
    }
}

// 初始化头节点并完成中序线索化
void inOrderThreading(ThreadTree *head, ThreadTree T)
{
    // 创建头节点（线索化的哨兵）
    *head = (ThreadTree)malloc(sizeof(ThreadNode));
    if (*head == NULL)
    {
        printf("内存分配失败\n");
        exit(1);
    }
    (*head)->ltag = 0;  // 头节点左指针指向根节点（孩子）
    (*head)->rtag = 1;  // 头节点右指针指向最后一个节点（线索）
    (*head)->rchid = *head;  // 初始右指针指向自身

    if (T == NULL)
    {
        // 空树：头节点左指针也指向自身
        (*head)->lchid = *head;
    }
    else
    {
        (*head)->lchid = T;  // 头节点左指针指向根节点
        prev = *head;        // 初始化prev为头节点（第一个节点的前驱是头节点）
        threading(T);        // 线索化整棵树

        // 处理最后一个节点的右线索：指向头节点
        prev->rtag = 1;
        prev->rchid = *head;
        // 头节点的右线索指向最后一个节点
        (*head)->rchid = prev;
    }
}

// 基于线索进行中序遍历（无需递归/栈，直接通过线索跳转）
void inOrder(ThreadTree head)
{
    ThreadTree curr = head->lchid;  // 从根节点开始

    while (curr != head)  // 循环直到回到头节点（遍历结束）
    {
        // 左孩子存在时，一直向左找最左节点（中序遍历起点）
        while (curr->ltag == 0)
        {
            curr = curr->lchid;
        }

        printf("%c", curr->data);  // 访问当前节点

        // 右指针是线索时，直接跳转到后继节点并访问
        while (curr->rtag == 1 && curr->rchid != head)
        {
            curr = curr->rchid;
            printf("%c", curr->data);
        }

        // 右指针是孩子时，转向右子树
        curr = curr->rchid;
    }
    printf("\n");
}

int main()
{
    ThreadTree head = NULL;  // 线索树的头节点（哨兵）
    ThreadTree T = NULL;     // 原始二叉树的根节点

    createTree(&T);          // 创建原始二叉树
    inOrderThreading(&head, T);  // 进行中序线索化
    inOrder(head);           // 基于线索遍历并输出

    return 0;
}
